package com.cty._04_Optimization._40_KLeastNumbers;

import com.sun.scenario.effect.impl.HeapImage;

/**
 * @Auther: cty
 * @Date: 2020/7/16 10:24
 * @Description: 面试题40：最小的k个数
 * 题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8
 * 这8个数字，则最小的4个数字是1、2、3、4。
 * @version: 1.0
 */
public class KLeastNumbers2 {

    /**
     * 方法二：最大数组堆实现，不改变数组，适用于海量数据
     * 时间复杂度：O(nlogk)
     * 空间复杂度：O(k)
     * @param array
     * @param length
     * @param k
     */
    public static void kLeastNumbers(int[] array, int length, int k){
        if(array==null || length<k || k<=0)
            return;

        HeapArray heap = new HeapArray(k);
        for(int i=0; i<length; i++)
            if(heap.size() < k)
                heap.insert(new DataItem(array[i]));
            else{
                int maxHeap = heap.findMax().getKey();
                if(array[i] < maxHeap){
                    heap.remove();
                    heap.insert(new DataItem(array[i]));
                }
            }  // end else

        heap.displayHeap();
    }  // end kLeastNumbers()


}  // end class
